COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a34.tex[106,phy] \today\hfill}

\bigskip
\line{{\bf Number Bases} [Assumes invariants]\hfill}
 
\bigskip
We use a number system with ten digits, where each place value
(1, 10, 100, 1000, etc.) is ten times as great as the previous one.
It probably doesn't surprise you to learn that every positive integer
can be written in this system, and that, excluding leading zeroes, there
is only one way to write it. Our use of the base ten is an accidental
result of our usual number of fingers and our habit of counting on them.
Any number from two on can be used as the base of a number system. Computers
almost universally use  two as their primary base, although they can be
programmed to calculate with any base. In later examples, we will use
one hundred thousand as a number base, so we will need to know a few
laws of arithmetic that apply using any base.

Suppose the base is the integer $b≥2$. Every positive integer~$P$ can be
broken into $a↓0+a↓1b+a↓2b↑2\cdots +a↓nb↑n$, with each $a↓i$ in the
range zero to $b-1$, $n≥0$, and $a↓n≠0$. The easiest way to show this
is to show an algorithm for getting $a↓0$, $a↓1$, $a↓2$, etc.

\smallskip\noindent
{\bf Example.} $P=1234$, $b=7$.
$$\vcenter{\halign{$\ctr{#}$\qquad&$\rt{#}$\qquad&$\rt{#}$\qquad&$\ctr{#}$\cr
I&P\phantom{34}&Q\phantom{6}&A\cr
\noalign{\smallskip}
0&1234&176&2\cr
1&176&25&1\cr
2&25&3&4\cr
3&3&0&3\cr
4&0\cr}}$$

In the top row, $P↓0$ is the given 1234. In row $I$, $Q↓I$ and $A↓I$
are respectively \hbox{$P↓I$ DIV 7} and \hbox{$P↓I$ MOD 7}, so
$P↓I=7Q↓I+A↓I$ and $0≤A↓I<7$. The value of $P↓{I+1}$, in the next row, is set
to~$Q↓I$. Taking all these relations together,
$$\eqalign{1234&=176\cdot 7+2\cr
176&=25\cdot 7+1\cr
25&=3\cdot 7+4\cr
(3&=0\cdot 7+3)\cr}$$
so
$$\eqalign{1234&=\bigl((3\cdot 7+4)\cdot 7+1\bigr)\cdot 7+2\cr
&=3\cdot 7↑3+4\cdot 7↑2+1\cdot 7+2\cr
&\qquad\hbox{which we abbreviate as $3412↓{(7)}$.}\cr}$$
The invariant of the algorithm is that $P↓I=A↓I+7A↓{I+1}+7↑2A↓{I+2}+\cdots
7↑{N-I}A↓N$, where $N$ is the line number on which~$Q↓N=0$.
We prove the invariant
by working backward; if it holds on line~$I$, it should hold on line~$I-1$:
$$\eqalign{P↓{I-1}&=A↓{I-1}+7Q↓{I-1}=A↓{I-1}+7P↓I\cr
&=A↓{I-1}+7(A↓I+7A↓{I+1}+7↑2A↓{I+2}+\cdots +7↑{N-I}A↓N)\cr
&=A↓{I-1}+7A↓I+7↑2A↓{I+1}+7↑3A↓{I+2}+\cdots +7↑{N-(I-1)}A↓N\,,\cr}$$
which is the result of putting $I-1$ for $I$ in the invariant. Putting
in 0 for~$I$,
$$P=P↓0=A↓0+7A↓1+7↑2A↓2+\cdots +7↑NA↓N\,.$$
There is nothing special about 7; any number greater than 2 (so that $Q↓I<P↓I$)
would work.

If the base is 10, we call $A↓0$, $A↓1$, etc., the {\sl digits\/} of the number,
but the word {\sl digit\/} (Latin for {\sl finger\/}) has so many associations
with the decimal system that I~hate to use it for other bases. Let's call
them {\sl bigits\/}.

Drill. Show that, if $P=B↓0+7B↓1+7↑2B↓2+\cdots +7↑MB↓M$, applying
the above algorithm to~$P$ gives $A↓0=B↓0$, $A↓1=B↓1$, $\ldots$ {}
$A↓M=B↓M$, $M=N$, so that there is no other way to write $P$ in the given base
\bblackslug

Given two numbers represented in base $b$,
$$\eqalign{P&=A↓0+A↓1b+A↓2b↑2+\cdots +A↓Nb↑N\cr
R&=D↓0+D↓1b+D↓2b↑2+\cdots +D↓Mb↑M\cr}$$
they can be added from left to right
by adding $A↓I+D↓I+$ the carry (zero or one) from the
next position to the right. The result can be anything from
$0+0+0=0$ to $(b-1)+(b-1)+1=2b-1$. If the result is $<b$, it is the next
bigit of the sum, and the next carry is zero. Otherwise, subtract $b$ from
the result to get the next bigit of the sum, and the next carry is one.
When you have used up the bigits of either number, use zeroes. When
you have used up the bigits of both numbers, quit as soon as the carry
is zero.

Positive numbers which are not integers can be represented, at least
approximately, in any base. By using $F$~fractional bigits, the number
can be expressed as 
$$P=A↓{-F}b↑{-F}+A↓{-(F-1)}b↑{-(F-1)}+\cdots +A↓{-1}b↑{-1}+
A↓0+A↓1b+\cdots +A↓Nb↑N\,.$$ 
The easiest way to get these bigits is to
multiply $P$ by~$b↑F$, (round or truncate to an integer), and write
the result as a base~$b$ number:
$$P\cdot b↑F=A↓{-F}+A↓{-(F-1)}b+\cdots +A↓{-1}b↑{F-1}+A↓0b↑F+A↓1b↑{F+1}
+\cdots +A↓Nb↑{F+N}\,.$$
The base $b$ representation is then written down with a ``decimal'' (or
binary or ternary or \dots) point as
$$A↓NA↓{N-1}A↓{N-1}\ldots A↓1A↓0.A↓{-1}A↓{-2}\ldots A↓{-F}\bblackslug$$
If the base $b$ is greater than ten, some of the digits $A↓i$ of a number
may be greater than~9, and writing them down without punctuation is
ambiguous. For example, in base~12,
$$\eqalign{157&=1+1\cdot 12+1\cdot 12↑2\hbox{ ``$=$'' }111↓{(12)}\cr
23&=11+1\cdot 12\hbox{ ``$=$'' }111↓{(12)}\cr
133&=1+11\cdot 12\hbox{ ``$=$'' }111↓{(12)}\bblackslug\cr}$$
We can resolve this in several ways. For one, we might use the letters
as extra bigits with values $A=10$, $B=11$, $\ldots$, $Z=35$, so that each
bigit is a single character, so long as $b≤36$:
$$\eqalign{157&=111↓{(12)}\cr
23&=1B↓{(12)}\cr
133&=B1↓{(12)}\bblackslug\cr}$$
We might punctuate the number, perhaps with vertical bars:
$$\eqalign{157&=1\,|\,1\,|\,1↓{(12)}\cr
23&=1\,|\,11↓{(12)}\cr
133&=11\,|\,1↓{(12)}\bblackslug\cr}$$
We might write each base-$b$ bigit as a decimal integer, with leading zeroes
if needed, of a standard length, using a space between the bigits:
$$\eqalign{157&=01\ 01\ 01↓{(12)}\cr
23&=01\ 11↓{(12)}\cr
133&=11\ 01↓{(12)}\bblackslug\cr}$$
If we go to a base, like 1000, which is a power of our usual base, we get
a pleasant surprise:
$$\eqalign{12345678&=1\cdot 10↑7+2\cdot 10↑6+3\cdot 10↑5+4\cdot 10↑4
+5\cdot 10↑3+6\cdot 10↑2+7\cdot 10+8\cr
&=(1\cdot 10+2)\cdot 10↑6+(3\cdot 10↑2+4\cdot 10+5)\cdot 10↑3+
(6\cdot 10↑2+7\cdot 10+8)\cr
&=12\cdot (10↑3)↑2+345\cdot 10↑3+678\cr
&=012\ 345\ 678↓{(1000)}\,;\cr}$$
the number looks just the way we always knew it, except that it is broken
up into bigit groups of a fixed number of characters, and padded on the
left with enough zeroes to make all the bigits the same length.

Why would we use such a large base? I use base 100000 when working by
hand with numbers too large for my pocket calculator. When adding,
the bigits are numbers less than 100000, so I~can add two bigits on the
calculator getting a base-100000 bigit (five decimal digits) of the
result at each step. I~can even multiply two bigits on the calculator,
getting a two-bigit (ten digit) result. Later programs will do other
arithmetic operations, like subtraction and division, on base-100000
numbers.




\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye